<html lang="zh-CN"><head><meta charset="UTF-8"><style>.nodata  main {width:1000px;margin: auto;}</style></head><body class="nodata " style=""><div class="main_father clearfix d-flex justify-content-center " style="height:100%;"> <div class="container clearfix " id="mainBox"><main><div class="blog-content-box">
<div class="article-header-box">
<div class="article-header">
<div class="article-title-box">
<h1 class="title-article" id="articleContentId">(B卷,100分)- AI面板识别（Java & JS & Python & C）</h1>
</div>
</div>
</div>
<div id="blogHuaweiyunAdvert"></div>

        <div id="article_content" class="article_content clearfix">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/kdoc_html_views-1a98987dfd.css">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/ck_htmledit_views-044f2cf1dc.css">
                <div id="content_views" class="htmledit_views">
                    <h4 id="main-toc">题目描述</h4> 
<p>AI识别到面板上有N&#xff08;1 ≤ N ≤ 100&#xff09;个指示灯&#xff0c;灯大小一样&#xff0c;任意两个之间无重叠。</p> 
<p>由于AI识别误差&#xff0c;每次别到的指示灯位置可能有差异&#xff0c;以4个坐标值描述AI识别的指示灯的大小和位置(左上角x1,y1&#xff0c;右下角x2,y2)&#xff0c;</p> 
<p>请输出先行后列排序的指示灯的编号&#xff0c;排序规则&#xff1a;</p> 
<ol><li>每次在尚未排序的灯中挑选最高的灯作为的基准灯&#xff0c;</li><li>找出和基准灯属于同一行所有的灯进行排序。两个灯高低偏差不超过灯半径算同一行&#xff08;即两个灯坐标的差 ≤ 灯高度的一半&#xff09;。</li></ol> 
<p></p> 
<h4 id="%E8%BE%93%E5%85%A5%E6%8F%8F%E8%BF%B0">输入描述</h4> 
<p>第一行为N&#xff0c;表示灯的个数<br /> 接下来N行&#xff0c;每行为1个灯的坐标信息&#xff0c;格式为&#xff1a;</p> 
<blockquote> 
 <p>编号 x1 y1 x2 y2</p> 
</blockquote> 
<ul><li>编号全局唯一</li><li>1 ≤ 编号 ≤ 100</li><li>0 ≤ x1 &lt; x2 ≤ 1000</li><li>0  ≤  y1 &lt; y2 ≤ 1000</li></ul> 
<p></p> 
<h4 id="%E8%BE%93%E5%87%BA%E6%8F%8F%E8%BF%B0">输出描述</h4> 
<p>排序后的编号列表&#xff0c;编号之间以空格分隔</p> 
<p></p> 
<h4 id="%E7%94%A8%E4%BE%8B">用例</h4> 
<table border="1" cellpadding="1" cellspacing="1" style="width:500px;"><tbody><tr><td style="width:86px;">输入</td><td style="width:412px;">5<br /> 1 0 0 2 2<br /> 2 6 1 8 3<br /> 3 3 2 5 4<br /> 5 5 4 7 6<br /> 4 0 4 2 6</td></tr><tr><td style="width:86px;">输出</td><td style="width:412px;">1 2 3 4 5</td></tr><tr><td style="width:86px;">说明</td><td style="width:412px;"><img alt="" height="190" src="https://img-blog.csdnimg.cn/5aa3fc1b616142208bd47595c57a024d.png" width="282" /></td></tr></tbody></table> 
<p></p> 
<p></p> 
<h4 id="%E9%A2%98%E7%9B%AE%E8%A7%A3%E6%9E%90">题目解析</h4> 
<p>题目给的图好像有问题&#xff0c;我画出来是</p> 
<p><img alt="" height="508" src="https://img-blog.csdnimg.cn/c23d295903a2412e907b6a8263300f89.png" width="631" /></p> 
<p>按照题目意思&#xff0c;每次取出一个最高的灯&#xff08;y坐标最小的&#xff09;&#xff0c;然后找出和最高灯坐标相差小于等于灯半径的&#xff0c;作为同一行&#xff0c;然后按照x轴坐标进行升序</p> 
<p>即存在如下用圈框住的三行&#xff0c;因此打印顺序是&#xff1a;1&#xff0c;2&#xff0c;3&#xff0c;4&#xff0c;5</p> 
<p><img alt="" height="545" src="https://img-blog.csdnimg.cn/3e8eb96d0f804acd925444fc8ff44ea7.png" width="666" /></p> 
<p></p> 
<p></p> 
<h4 id="%E7%AE%97%E6%B3%95%E6%BA%90%E7%A0%81">Java算法源码</h4> 
<pre><code class="language-java">import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
import java.util.StringJoiner;

public class Main {
  public static void main(String[] args) {
    Scanner sc &#61; new Scanner(System.in);

    int n &#61; sc.nextInt();

    Light[] lights &#61; new Light[n];
    for (int i &#61; 0; i &lt; n; i&#43;&#43;) {
      int id &#61; sc.nextInt();
      int x1 &#61; sc.nextInt();
      int y1 &#61; sc.nextInt();
      int x2 &#61; sc.nextInt();
      int y2 &#61; sc.nextInt();
      lights[i] &#61; new Light(id, (x1 &#43; x2) / 2, (y1 &#43; y2) / 2, (x2 - x1) / 2);
    }

    System.out.println(getResult(lights));
  }

  public static String getResult(Light[] lights) {
    // 按照圆心y坐标升序
    Arrays.sort(lights, (a, b) -&gt; a.y - b.y);

    // ans记录题解
    StringJoiner ans &#61; new StringJoiner(&#34; &#34;);

    // sameRowLights记录同一行的灯
    ArrayList&lt;Light&gt; sameRowLights &#61; new ArrayList&lt;&gt;();
    Light base &#61; lights[0];
    sameRowLights.add(base);

    for (int i &#61; 1; i &lt; lights.length; i&#43;&#43;) {
      Light light &#61; lights[i];

      // 如果lights[i]的纵坐标和base的纵坐标相差不超过半径&#xff0c;则视为同一行
      if (light.y - base.y &lt;&#61; base.r) {
        sameRowLights.add(light);
      } else {
        // 否则&#xff0c;不是同一行
        // 针对同一行的灯&#xff0c;再按照横坐标升序
        sameRowLights.sort((a, b) -&gt; a.x - b.x);
        sameRowLights.forEach(a -&gt; ans.add(a.id &#43; &#34;&#34;));
        sameRowLights.clear();

        // 开始新的一行记录
        base &#61; light;
        sameRowLights.add(base);
      }
    }

    // 注意不要漏了最后一行
    if (sameRowLights.size() &gt; 0) {
      sameRowLights.sort((a, b) -&gt; a.x - b.x);
      sameRowLights.forEach(a -&gt; ans.add(a.id &#43; &#34;&#34;));
    }

    return ans.toString();
  }
}

class Light {
  int id; // 编号
  int x; // 圆心横坐标
  int y; // 圆心纵坐标
  int r; // 圆半径

  public Light(int id, int x, int y, int r) {
    this.id &#61; id;
    this.x &#61; x;
    this.y &#61; y;
    this.r &#61; r;
  }
}
</code></pre> 
<p></p> 
<h4>JS算法源码</h4> 
<pre><code class="language-javascript">/* JavaScript Node ACM模式 控制台输入获取 */
const readline &#61; require(&#34;readline&#34;);

const rl &#61; readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines &#61; [];
let n;
rl.on(&#34;line&#34;, (line) &#61;&gt; {
  lines.push(line);

  if (lines.length &#61;&#61;&#61; 1) {
    n &#61; lines[0] - 0;
  }

  if (n &amp;&amp; lines.length &#61;&#61; n &#43; 1) {
    lines.shift();

    const lights &#61; lines.map((line) &#61;&gt; {
      const [id, x1, y1, x2, y2] &#61; line.split(&#34; &#34;).map(Number);
      return new Light(id, (x1 &#43; x2) &gt;&gt; 1, (y1 &#43; y2) &gt;&gt; 1, (x2 - x1) &gt;&gt; 1);
    });

    console.log(getResult(lights));

    lines.length &#61; 0;
  }
});

class Light {
  constructor(id, x, y, r) {
    this.id &#61; id; // 编号
    this.x &#61; x; // 圆心横坐标
    this.y &#61; y; // 圆心纵坐标
    this.r &#61; r; // 圆半径
  }
}

function getResult(lights) {
  // 按照圆心y坐标升序
  lights.sort((a, b) &#61;&gt; a.y - b.y);

  // ans记录题解
  const ans &#61; [];

  // sameRowLights记录同一行的灯
  const sameRowLights &#61; [];
  let base &#61; lights[0];
  sameRowLights.push(base);

  for (let i &#61; 1; i &lt; lights.length; i&#43;&#43;) {
    const light &#61; lights[i];

    // 如果lights[i]的纵坐标和base的纵坐标相差不超过半径&#xff0c;则视为同一行
    if (light.y - base.y &lt;&#61; base.r) {
      sameRowLights.push(light);
    } else {
      // 否则&#xff0c;不是同一行
      // 针对同一行的灯&#xff0c;再按照横坐标升序
      sameRowLights.sort((a, b) &#61;&gt; a.x - b.x).forEach((a) &#61;&gt; ans.push(a.id));
      sameRowLights.length &#61; 0;

      // 开始新的一行记录
      base &#61; light;
      sameRowLights.push(base);
    }
  }

  // 注意不要漏了最后一行
  if (sameRowLights.length &gt; 0) {
    sameRowLights.sort((a, b) &#61;&gt; a.x - b.x).forEach((a) &#61;&gt; ans.push(a.id));
    sameRowLights.length &#61; 0;
  }

  return ans.join(&#34; &#34;);
}
</code></pre> 
<p></p> 
<h4>Python算法源码</h4> 
<pre><code class="language-python">class Light:
    def __init__(self, id, x, y, r):
        self.id &#61; id  # 编号
        self.x &#61; x  # 圆心横坐标
        self.y &#61; y  # 圆心纵坐标
        self.r &#61; r  # 圆半径


# 输入获取
n &#61; int(input())
arr &#61; [list(map(int, input().split())) for _ in range(n)]
lights &#61; list(map(lambda ele: Light(ele[0], (ele[1] &#43; ele[3]) // 2, (ele[2] &#43; ele[4]) // 2, (ele[3] - ele[1]) // 2), arr))


# 算法入口
def getResult():
    # 按照圆心y坐标升序
    lights.sort(key&#61;lambda l: l.y)

    # ans记录题解
    ans &#61; []

    # sameRowLights记录同一行的灯
    sameRowLights &#61; []
    base &#61; lights[0]
    sameRowLights.append(base)

    for i in range(1, len(lights)):
        light &#61; lights[i]

        # 如果lights[i]的纵坐标和base的纵坐标相差不超过半径&#xff0c;则视为同一行
        if light.y - base.y &lt;&#61; base.r:
            sameRowLights.append(light)
        else:
            # 否则&#xff0c;不是同一行
            # 针对同一行的灯&#xff0c;再按照横坐标升序
            sameRowLights.sort(key&#61;lambda l: l.x)
            for l in sameRowLights:
                ans.append(l.id)
            sameRowLights.clear()

            # 开始新的一行记录
            base &#61; light
            sameRowLights.append(base)

    # 注意不要漏了最后一行
    if len(sameRowLights) &gt; 0:
        sameRowLights.sort(key&#61;lambda l: l.x)
        for l in sameRowLights:
            ans.append(l.id)

    return &#34; &#34;.join(map(str, ans))


# 算法调用
print(getResult())
</code></pre> 
<h4>C算法源码</h4> 
<pre><code class="language-cpp">#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
#include &lt;string.h&gt;

#define MAX_SIZE 100

// 灯信息结构体
typedef struct {
    int id; // 灯id
    int x; // 灯的横坐标
    int y; // 灯的纵坐标
    int r; // 灯的半径
} Light;

// 记录题解
char res[100000];

int cmp(const void *a, const void *b) {
    // 按照灯的圆心y坐标升序
    return ((Light *) a)-&gt;y - ((Light *) b)-&gt;y;
}

int cmp2(const void *a, const void *b) {
    // 针对同一行的灯&#xff0c;按照圆心x坐标升序
    return ((Light *) a)-&gt;x - ((Light *) b)-&gt;x;
}

void joinToRes(Light sameRowLights[], int sameRowLights_size) {
    qsort(sameRowLights, sameRowLights_size, sizeof(Light), cmp2);

    for (int j &#61; 0; j &lt; sameRowLights_size; j&#43;&#43;) {
        char tmp[100];
        sprintf(tmp, &#34;%d&#34;, sameRowLights[j].id);
        strcat(res, tmp);
        strcat(res, &#34; &#34;);
    }
}

int main() {
    // 灯的个数
    int n;
    scanf(&#34;%d&#34;, &amp;n);

    Light lights[MAX_SIZE];
    for (int i &#61; 0; i &lt; n; i&#43;&#43;) {
        // 灯编号&#xff0c;以及坐标信息
        int id, x1, y1, x2, y2;
        scanf(&#34;%d %d %d %d %d&#34;, &amp;id, &amp;x1, &amp;y1, &amp;x2, &amp;y2);

        lights[i].id &#61; id;
        lights[i].x &#61; (x1 &#43; x2) / 2;
        lights[i].y &#61; (y1 &#43; y2) / 2;
        lights[i].r &#61; (x2 - x1) / 2;
    }

    // 同一行的灯集合
    Light sameRowLights[MAX_SIZE];
    int sameRowLights_size &#61; 0;

    // 按照圆心y坐标升序
    qsort(lights, n, sizeof(Light), cmp);

    // sameRowLights记录同一行的灯
    Light base &#61; lights[0];
    sameRowLights[sameRowLights_size&#43;&#43;] &#61; base;

    for (int i &#61; 1; i &lt; n; i&#43;&#43;) {
        Light light &#61; lights[i];

        // 如果lights[i]的纵坐标和base的纵坐标相差不超过半径&#xff0c;则视为同一行
        if (light.y - base.y &lt;&#61; base.r) {
            sameRowLights[sameRowLights_size&#43;&#43;] &#61; light;
        } else {
            // 否则&#xff0c;不是同一行
            // 针对同一行的灯&#xff0c;再按照横坐标升序
            joinToRes(sameRowLights, sameRowLights_size);

            // 开始新的一行记录
            sameRowLights_size &#61; 0;
            base &#61; light;
            sameRowLights[sameRowLights_size&#43;&#43;] &#61; base;
        }
    }

    // 注意不要漏了最后一行
    if (sameRowLights_size &gt; 0) {
        joinToRes(sameRowLights, sameRowLights_size);
    }

    // joinToRes中会在res最后多拼接一个空格&#xff0c;这里去掉
    res[strlen(res) - 1] &#61; &#39;\0&#39;;

    puts(res);

    return 0;
}



</code></pre>
                </div>
        </div>
        <div id="treeSkill"></div>
        <div id="blogExtensionBox" style="width:400px;margin:auto;margin-top:12px" class="blog-extension-box"></div>
    <script>
  $(function() {
    setTimeout(function () {
      var mathcodeList = document.querySelectorAll('.htmledit_views img.mathcode');
      if (mathcodeList.length > 0) {
        for (let i = 0; i < mathcodeList.length; i++) {
          if (mathcodeList[i].naturalWidth === 0 || mathcodeList[i].naturalHeight === 0) {
            var alt = mathcodeList[i].alt;
            alt = '\\(' + alt + '\\)';
            var curSpan = $('<span class="img-codecogs"></span>');
            curSpan.text(alt);
            $(mathcodeList[i]).before(curSpan);
            $(mathcodeList[i]).remove();
          }
        }
        MathJax.Hub.Queue(["Typeset",MathJax.Hub]);
      }
    }, 1000)
  });
</script>
</div></html>